import java.util.Arrays;
import java.util.Stack;

public class Test {
    /**
     * 快排
     * 时间复杂度：O(nlogN)
     * 空间复杂度：O(logN)
     * 稳定性：不稳定
     */
    //Hoare法
    public void quickSort(int[] arr, int left, int right){
        if(left > right) return;

        int mid = midOfThree(arr,left,right);
        swap(arr,mid,left);

        swap(arr,left,mid);
        int div = partition2(arr, left, right);
        quickSort(arr,left,div-1);
        quickSort(arr,div+1,right);
    }
    public int midOfThree(int[] arr, int left, int right){
        int mid = left + (right-left)/2;
        if(arr[left] < arr[right]){
            if(arr[left] > arr[mid]){
                return left;
            }else if(arr[mid] > arr[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if(arr[left] < arr[mid]){
                return left;
            }else if(arr[right] > arr[mid]){
                return right;
            }else {
                return mid;
            }
        }
    }
    public int partition(int[] arr, int left, int right){
        int tmp = left;
        int key = arr[left];
        while(left < right){
            while(left < right && arr[right] >= key){
                right--;
            }
            while(left < right && arr[left] <= key){
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,tmp,left);
        return left;//or right
    }
    //挖坑法
    public int partition1(int[] arr, int left, int right){
        int tmp = arr[left];
        while(left < right){
            while(left < right && arr[right] >= tmp){//=必须有 ， 必须是right先走
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= tmp){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
    //指针法
    public int partition2(int[] arr, int left, int right){
        int prev = left;
        int cur = left + 1;
        while(cur <= right){
            if(arr[cur] < arr[left] && (++prev) != cur ){
                swap(arr,prev,cur);
            }
            cur++;
        }
        swap(arr,left,prev);
        return prev;
    }
    //非递归写法
    public void quickSortNor(int[] arr, int left, int right){
        Stack<Integer> ret = new Stack<>();
        ret.push(left);
        ret.push(right);
        while(!ret.empty()){
            right = ret.pop();
            left = ret.pop();
            int div = partition(arr,left,right);
            if(left + 1 < div){
                ret.push(left);
                ret.push(div-1);
            }
            if(right-1 > div){
                ret.push(div+1);
                ret.push(right);
            }
        }
    }
    public void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[][] a = {{1,7},{8,9},{4,74}};
        System.out.println(Arrays.toString(a));
    }
}
